package com.lfg.leetcode.leetcode0;

public class No79exist {

    public static void main(String[] args) {
        char[][] array = new char[2][2];
        array[0] = new char[]{'a', 'b'};
        array[1] = new char[]{'d', 'c'};
        boolean ret = exist(array, "da");
        System.out.println("[" + ret + "]");
    }

    public static boolean exist(char[][] board, String word) {
        if (board.length == 0) {
            return false;
        }
        if (board[0].length == 0) {
            return false;
        }
        if (null == word || "".equals(word)) {
            return false;
        }
        boolean[][] flag = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (exist(board, flag, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean exist(char[][] board, boolean[][] flag, String word, int x, int y, int index) {
        if (word.length() == index) {
            return true;
        }
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
            return false;
        }
        if (flag[x][y]) {
            return false;
        }
        if (board[x][y] != word.charAt(index)) {
            return false;
        }
        flag[x][y] = true;
        boolean ret = exist(board, flag, word, x + 1, y, index + 1) || exist(board, flag, word, x - 1, y, index + 1)
                || exist(board, flag, word, x, y + 1, index + 1) || exist(board, flag, word, x, y - 1, index + 1);
        flag[x][y] = false;
        return ret;
    }


}

